#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

int getMoneyAmount(int n);

int main()
{
	return 0;
}

int getMoneyAmount(int n)
{
	int f[n + 1][n + 1];
	memset(f, 0, sizeof(f));
	for (int col = n - 1; col >= 1; col--)
		for (int row = col + 1; row <= n; row++) {
			int minCost = INT_MAX;
			for (int i = col; i < row; i++) {
				int cost = i + fmax(f[col][i - 1], f[i + 1][row]);
				minCost = fmin(minCost, cost);
			}
			f[col][row] = minCost;
		}

	return f[1][n];
}
